package com.ruoyi.learn.java.algorithm.sort;

public class SelectionSort {
    // 选择排序方法

    /**
     * 选择排序的工作原理：
     * 将数组分为已排序和未排序两部分，初始时已排序部分为空
     * 在未排序部分中找到最小（或最大）元素
     * 将找到的最小元素与未排序部分的第一个元素交换位置
     * 此时已排序部分增加一个元素，未排序部分减少一个元素
     * 重复步骤 2-4，直到所有元素都加入已排序部分
     * 选择排序的复杂度分析：
     * 时间复杂度：无论最好、最坏还是平均情况，都是 O (n²)，因为它总是需要完整遍历未排序部分
     * 空间复杂度：O (1)，属于原地排序算法
     * 稳定性：不稳定的排序算法，可能会改变相等元素的相对顺序
     * 选择排序的交换操作次数较少（最多 n-1 次），这是它相比冒泡排序的一个优势，但比较操作次数仍然较多，适合简单场景或教学演示。
     * @param arr
     */
    public static void selectionSort(int[] arr) {
        int n = arr.length;

        // 外层循环控制需要排序的位置
        for (int i = 0; i < n - 1; i++) {
            // 找到未排序部分中的最小元素索引
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j; // 更新最小元素索引
                }
            }

            // 将找到的最小元素与未排序部分的第一个元素交换
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    // 打印数组的方法
    public static void printArray(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // 主方法，用于测试
    public static void main(String[] args) {
        int[] testArray = {64, 25, 12, 22, 11};
        System.out.println("排序前的数组:");
        printArray(testArray);

        // 调用选择排序
        selectionSort(testArray);

        System.out.println("排序后的数组:");
        printArray(testArray);
    }
}
